#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

//数据流中的中位数，大根堆存放较小的一半的数，小根堆存放较大的一半的数
class Solution
{
private:
    priority_queue<int> big;
    priority_queue<int, vector<int>, greater<int>> small;
    int k = 0;

public:
    void Insert(int num)
    {
        ++k;
        big.push(num);
        small.push(big.top());
        big.pop();
        if (k % 2 == 0)
        {
            big.push(small.top());
            small.pop();
        }
    }

    double GetMedian()
    {
        if (k % 2 == 0)
        {
            return (double)(big.top() + small.top()) / 2;
        }
        else
        {
            return small.top();
        }
    }
};

void test()
{
}

int main()
{
    test();
    return 0;
}